package com.gali.leetcode.day24;

import java.util.*;

/**
 * @Auther: gali
 * @Date: 2022-08-15 19:52
 * @Description:
 */
public class Solution {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

          /**
           * 二叉树的层序遍历
           * @param root
           * @return
           */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        //trackToTreeNode(lists,root,0);
//        if (root==null){
//            return lists;
//        }
//        Queue<TreeNode> queue=new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()){
//            List<Integer> list=new ArrayList<>();
//            for (int i = 0; i < queue.size(); i++) {
//                TreeNode poll = queue.poll();
//                list.add(poll.val);
//                if (poll.left!=null){
//                    queue.offer(poll.left);
//                }
//                if (poll.right!=null){
//                    queue.offer(poll.right);
//                }
//            }
//            lists.add(list);
//        }
//        return lists;
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
    }

          /**
           * 递归
           * @param lists
           * @param root
           * @param i
           */
          private void trackToTreeNode(List<List<Integer>> lists, TreeNode root, int i) {
            if (root==null){
                return;
            }
            if (lists.size()==i){
                lists.add(new ArrayList<Integer>());
            }
            lists.get(i).add(root.val);
            trackToTreeNode(lists,root.left,i+1);
            trackToTreeNode(lists,root.right,i+1);
          }
      }

